Round Overview
Discuss this match
SRM 607 was the first contribution of Wheeler. A problem set that focused on dynamic programming and clever optimization. The division 1 coders began their journey dealing with a classical string problem. Then they had to face the reality of an complicated problem that could become much simpler through observation. Finally, the beautiful division 1 hard that was a fractal of deeper and deeper algorithmic challenges. This problem wasn’t solved by any of the coders, and lyrically was the only coder that was able to submit a solution at all. The division winners would be decided by the first two problems. Through marvellous speed at those problems, tomek got the first place with a relevant lead over other big names like K.A.D.R (2nd place), Petr (3rd place) and tourist (4th place). Congratulations also to division 2 winner: enrevol.
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 1011 / 1103 (91.66%) |
Success Rate | 973 / 1011 (96.24%) |
High Score | AravindKumar07 for 249.96 points (0 mins 21 secs) |
Average Score | 215.75 (for 973 correct submissions) |
This is a classical problem, the minimum bounding box problem. The trick to this problem is to notice that the bottom-left corner of the rectangle is point `(min(x_i),min(y_i))` where `min(x_i)` is the minimum `x` coordinate among the points and the top right corner is `(max(x_i), max(y_i))`.
The area of the rectangle is equal to the product of its height and width. The height is the difference between corners’ `y` coordinates and the width is the difference between corners’ `x` coordinates. The result will therefore be: `(max(x_i) - min(x_i)) times (max(y_i) - min(y_i))`.
We can find the minimums/maximums with a single loop and then return the area, like in the following Java solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class BoundingBox {
public int smallestArea(int[] X, int[] Y) {
//use element 0 as initial value
int minx = X[0];
int maxx = X[0];
int miny = Y[0];
int maxy = Y[0];
for (int i = 1; i < Y.length; i++) {
minx = Math.min(minx, X[i]);
maxx = Math.max(maxx, X[i]);
miny = Math.min(miny, Y[i]);
maxy = Math.max(maxy, Y[i]);
}
return (maxx - minx) * (maxy - miny);
}
}
As is usual with division 2 level 1 problems, knowledge of the tools at our disposals can save up precious coding time and improve the score. The languages have functions that can help us here. We could sort the arrays and then use element 0 as the minimum and the last element as the maximum. Or like in the following c++ and python examples, we could use functions that directly get the maximum and minimum of a vector/tuple.
1
2
3
4
5
6
7
int smallestArea(vector < int > X, vector < int > Y) {
int minx = * min_element(X.begin(), X.end());
int maxx = * max_element(X.begin(), X.end());
int miny = * min_element(Y.begin(), Y.end());
int maxy = * max_element(Y.begin(), Y.end());
return (maxx - minx) * (maxy - miny);
}
1
2
3
class BoundingBox:
def smallestArea(self, X, Y):
return (max(X) - min(X)) * (max(Y) - min(Y))
PalindromicSubstringsDiv2
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 828 / 1103 (75.07%) |
Success Rate | 280 / 828 (33.82%) |
High Score | ashashwat for 495.29 points (2 mins 46 secs) |
Average Score | 334.06 (for 280 correct submissions) |
The straightforward solution is to take every substring of the string - there are `O(n^2)` substrings. For each substring, check if it is palindrome. Checking if a string of length `t` is palindrome requires us to test each pair of opposite indexes in the string, giving an `O(t)` algorithm. Since `t` is `O(n)` then the complexity for this straightforward algorithm is `O(n^3)`. `n <= 5000`, so it will be too slow.
How can we improve the time complexity?
Consider a string `s` like “ABBCDCBBA” and the algorithm we use to check if it is palindrome:
1
2
0 1 2 3 4 5 6 7 8
A B B C D C B B A
The first step is to compare `s[0]` with `s[8]`, if they are not equal, we can stop the algorithm - the string is not palindrome. Else we need to compare the remaining indexes: `s[1]` with `s[7]` then `s[2]` with `s[6]`, etc. Another way to look at this is recursively, we first compare `s[0]` with `s[8]`, then the remaining indexes make a new smaller instance of the original problem. If “BBCDCBB” is palindrome and s[0]=“A”=s[8] then the string is palindrome.
So we can define a function `f(a,b)` that checks if the substring original `S` containing characters from `a` to `b-1` is palindrome.
If `a = b`, string is empty, if `a = b - 1`, the string contains 1 character. In both cases, the string is palindrome. (Base case).
Else if `s[a] = s[b-1]`, then the string is palindrome if the substring starting at `a+1` and finishing at `b-2` is palindrome. So we call `f(a+1,b-1)` to find out if it is palindrome.
If `s[a] != s[b-1]`, the string is not palindrome.
So now that we understand the recursive algorithm to check if a string is palindrome. We can go back to the original problem. For each substring of `S`, we ask if it is palindrome, meaning that we call an `f(a,b)`. Because of the recursive nature of the string, `f()` will be called multiple times for many substring `[a,b)`. But what if we use memoization? Then we can ensure that each call to `f()` will be evaluated exactly once. Since there are `O(n^2)` substrings, this will guarantee that the overall time complexity is `O(n^2)`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
string s;
char dp[5000][5001];
// Returns true if the substring [a, b) is palindrome.
bool isPalindrome(int a, int b) {
char & res = dp[a][b];
if (res == -1) {
if (b - a <= 1) {
// string is empty or has one character, result is true
res = true;
} else {
if (s[a] == s[b - 1]) {
res = isPalindrome(a + 1, b - 1);
} else {
res = false;
}
}
}
return res;
}
int count(string s) /* assume we already generated string s from S1 and S2 */ {
this - > s = s;
int n = s.length();
int res = 0;
// For memoization, we fill dp[][] with -1.
memset(dp, -1, sizeof(dp));
// For each substring:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (isPalindrome(i, j)) {
res++;
}
}
}
return res;
}
An issue with that solution is the array that needs `O(n^2)` memory. The allocation can be problematic or take extra time in some languages. We can solve the problem in `O(1)` memory by solving the recursion iteratively. Or we can come up to the iterative version directly. Back to the example:
1
2
0 1 2 3 4 5 6 7 8
A B B C D C B B A
What if we do the checks in reverse? First begin with index 4, it is a single string that is already a palindrome, so we can increase the count. Then we have two pointers `i = 3` and `j = 5`, check `s[i] = s[j]`, If they are still equal, we have a new palindrome string and increase the count. Then decrement `i`. , increment `j`, check again and so and so. Note that the starting middle point can be any of the `O(n)` indexes of the string, and that there are even substrings so sometimes the starting point is a single character and sometimes two.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int count(string s) {
int n = s.length();
int res = 0;
// pick the middle point m:
for (int m = 0; m < n; m++) {
// Try an odd-length substring (even == 0), and also an even-length one (even == 1):
for (int even = 0; even < 2; even++) {
int i, j;
// initialize pointers depending on even or not:
bool pal = true;
if (even == 1) {
i = m;
j = m + 1;
res++;
} else {
i = m - 1;
j = m + 1;
}
// do the check:
while ((i >= 0) && (j < n)) {
pal = (pal && (s[i] == s[j]));
if (pal) {
res++;
}
i--;
j++;
}
}
}
return res;
}
CombinationLockDiv2
Problem Details
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 49 / 1103 (4.44%) |
Success Rate | 3 / 49 (6.12%) |
High Score | zhangchenxu for 449.89 points (45 mins 26 secs) |
Average Score | 423.49 (for 3 correct submissions) |
This (specially the division 1 version) is a problem in which it is easy to make assumptions that are wrong. It is best not to take advantage of properties/limitations that we cannot prove.
An idea that is not necessary but will simplify the code is to notice that we do not really care about the specific values of the digits in s or t, but just about the distance between each s[i] and t[i]. We can turn the problem into one in which we should convert all digits to 0. For example, the steps that can take `s_i = 4` to `t_i = 9`, are the same steps that can take `d_i = 5` to 0. Similar to finding the distance between angles in a circle, this needs modular arithmetic: `d_i -= (s_i - t_i) mod 10`. The problem becomes about turning those `d_i` values into 0.
There *is* a property that we can prove and can greatly simplify the problem. Imagine a sequence of moves in which we moved all numbers in many intervals up or down. If two intervals overlap and the directions of the intervals are different, they would cancel out:
1 2 3
d = 13749920384994(move) ++ ++ ++ d = 13750031484994(move) -- -- - d = 13750030373883
That sequence of moves is equivalent to:
1
2
3
d = 13749920384994(move) ++ ++
d = 13750030384994(move) -- -
d = 13750030373883
Which do not overlap. It may at first appear that there are cases in which an overlap might be useful. Like Splitting a large interval in two halves:
1 2 3
d = 13749920384994(move) ++ ++ ++ ++ ++ ++ d = 14850031493004(move) - d = 14850021493004
But in reality, we can still reach the same state in two moves that don’t overlap. What about a more formal proof? Whenever two intervals `A` and `B` of different direction overlap, it costs 2 moves. Using set operations, the two moves can be replaced by other two moves: `A - (A nnn B)` (in same direction as `A`) and `B - (A nnn B)` (in same direction as `B`. The resulting digits are the same and the cost is also the same. If there are any more overlaps, we can repeat this simplification until there are no overlaps.
If we wanted to make a dynamic programming solution, we should first find an “optimal substructure” in this problem. The issue is that all those overlap those intervals make the problem too tangled. This is why we need to think in terms of opening and closing intervals.
Let us say we move from the lowest indexed digit to the highest, and decide, for each of them, the direction and the number of times to rotate the dial. We can only choose direction/number combinations that make the digit 0. Imagine the decision is like this: `(+22, +12, +1, -7, -6, -11)`, meaning first digit moves 22 up, second digit 12 times up, fourth digit 7 times down and so and so. Note that we are moving some digits more than 9 times. It is tempting to make the assumption that you only need to move each digit at most 9 times, but that assumption is wrong (Very wrong, there are test cases in which the number of times we need to move a single digit is `2n`). Let’s avoid any risk and just use `9n` as the maximum number of times a single digit may move (This is a very safe bound, because all test cases can be solved in at most `9n` steps).
With moves like `(+22, +12, +1)`, what is the minimum number of intervals that cover all those moves? We can make a single interval over the 3 digits, then 11 intervals that cover the first two digits and 9 more intervals for the first digit. A way to interpret this is that we decided that 22 intervals must go through the first digit, 12 intervals through the second digit and only 1 through the third digit. How about we changed the decision from picking the number of intervals in each digit to picking the number of new intervals added for that digit? (Possibly, we could also close intervals), then the cost only increases by the number of intervals we open in that digit.
Another example: `(+1,+2,+3,+4,+3,+2,+1)`: First we open an interval for the first digit. Second digit needs 2 intervals, which means we open a new interval. And so and so, eventually we move from `+4` to `+3`, this means closing one interval, so it doesn’t add to the cost. In total, we open 4 intervals, which means it can be solved with 4 intervals:
1 2 3 4
+ ++ + ++ ++ + ++ ++ ++ +
When the intervals are negative, they behave in the same way, but this time the intervals make the digits decrease.
Let us decide the direction and number of intervals for each digit in increasing order of index. We need to remember the number of open intervals `x`, and the direction `u`. If `u=1`, the direction is up, if `u=0` the direction is down. `f(p, x, u)` returns the minimum cost to zero the digits with index greater than or equal to `p` if the number of open intervals after deciding the first `p` digits is `x` and their direction is `u`.
Base case: `p = n`, we have set all the digits to 0. Nothing to do, the minimum cost is 0.
Else we pick a new direction `n_u` and a new number of intervals `y`:
If the directions are different, we are forced to open `y` new intervals. Cost is `y + f(p+1, y, n_u)`.
Else the number of new intervals is either `y - x` (if `y>x`) or 0 (otherwise). Cost is: `max(y-x,0) + f(p+1, y, u)`
Pick the minimum cost out of all the options.
We use dynamic programming so that each state of the function is evaluated at most once. There are `n+1` values for `p` and the maximum number of moves per digit is `9n`. There are `2*(n+1)*9*n` states in the function and each needs to try `2*9n` options. The complexity order is `O(n^3)`, but there are some sizable factors (9*9*2*2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
static
const int INF = 1000000000;
static
const int MAX_N = 50;
static
const int MAX_OP = 450;
vector < int > d;
int n;
int dp[MAX_N + 1][MAX_OP + 1][2];
int rec(int p, int x, int up) {
int & res = dp[p][x][up];
if (res == -1) {
if (p == n) {
res = 0;
} else {
res = INF;
// pick direction and number of changes:
for (int nu = 0; nu <= 1; nu++) {
for (int y = 0; y <= MAX_OP; y++) {
// verify the new direction and mumber of moves will set
// the digit to 0:
if (nu == 0) {
if ((d[p] + 9 * y) % 10 != 0) {
//invalid
continue;
}
} else {
if ((d[p] + y) % 10 != 0) {
//invalid
continue;
}
}
int z = 0;
if (nu != up) {
// must open new intervals
z = y;
} else {
z = max(y - x, 0);
}
res = std::min(res, z + rec(p + 1, y, nu));
}
}
}
}
return res;
}
int minimumMoves(string s, string t) {
n = s.size();
d.resize(n);
for (int i = 0; i < n; i++) {
if (s[i] >= t[i]) {
d[i] = s[i] - t[i];
} else {
d[i] = s[i] + 10 - t[i];
}
}
memset(dp, -1, sizeof(dp));
return rec(0, 0, 0);
}
PalindromicSubstringsDiv1
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 537 / 720 (74.58%) |
Success Rate | 400 / 537 (74.49%) |
High Score | ACMonster for 246.06 points (3 mins 36 secs) |
Average Score | 177.90 (for 400 correct submissions) |
This appears to be a complicated issue. The number of substrings depends on the values of possibly many characters, which are shared between the substrings. How to deal with this dependency? This requires a trick that is becoming common in problems asking for the expected value of a random variable that depends on some sum: The linearity of expectation.
In short, the expected value of a sum of variables is equal to the sum of the expected values of the variables. We first need to express the result we want to calculate as a sum. For each substring of `S`, we determine if it is a palindrome and if so, we add 1 to the result. We can formalize this by creating a function `f(s)` that returns 1 if substring `s` is substring and zero otherwise:
`r = sum_(s in (“substrings of S”))( f(s) )`
We use the linearity of expectation:
`E® = sum_(s in (“substrings of S”))( E(f(s)) )`
The wonderful thing about linearity of expectation is that it works whether or not the added variables are independent. So this effectively divides the problem into many independent subproblems specific to each substring.
What does `E(f(s))` mean? By definition. expected value of `f(s)` is equal to the sum of each possible value of `f(s)` multiplied by the probability that `f(s)` happens. The two possible values for `f(s)` are 0 and 1, multiply 0 by anything will nullify it:
`E(f(s)) = 1 * P[ f(s) is 1]`
`E(f(s)) = P[ “s is a palindrome” ]`
So now we just need to find, for each substring, the probability it will be palindrome , their sum is the expected number of palindrome substrings.
`E® = sum_(s in (“substrings of S”))( P[ “s is a palindrome” ] )`
Now we have a new problem: For each of the `O(n^2)` substrings, we need to calculate the probability they will be palindromic.
Given a string containing some question marks, how can you find the probability? It is similar to the usual [check if string is palindrome] algorithm in which we use two pointers:
1
2
0 1 2 3 4 5 6 7 8
A B ? C ? C ? ? A
First compare `s[8]` with `s[0]`. It could happen that neither of them is a question mark. This means that the characters are fixed. For the string to be palindromic, they need to be equal. The probability they are equal is 1.00 if they are and 0.00 if they are not. In this case, both are “A”
Now compare `s[1]` with `s[7]`, this time one of them is ? and the other is fixed to “B”. For the string to be palindromic, the ? needs to become “B”. Exactly one valid option out of 26: `1/26` probability.
When comparing `s[2]` with `s[6]`, both are “?”, there are two choices of 26 letters and we need the two to be equal. The second character needs to be equal to the first one, so there is also one valid option out of 26: `1/26`.
Eventually we reach `s[4]`, this time the string has odd length, so this is the last character of the string and it is already equal to itself, even if it was fixed or not, the probability is 1.0.
Each pair of opposite indexes makes a single event, so the total probability the string is palindrome is equal to the product of all the probabilities for each pair of opposite indexes.
With this approach, we need an `O(n)` algorithm for each of the `O(n^3)` strings. That is going to be too much. However, we can use the same tricks we used in the division 2 version to make an `O(n^2)` algorithm. For example, we can pick each of the `O(n)` middle indexes, and for each of them, expand the string one step at a time as we calculate the probabilities and add them to the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
double expectedPalindromes(string s) {
int n = s.length();
double res = 0;
// pick the middle point m:
for (int m = 0; m < n; m++) {
// Try an odd-length substring (even == 0), and also an even-length one (even == 1):
for (int even = 0; even < 2; even++) {
int i, j;
// initialize pointers depending on even or not:
double p = 1.0;
if (even == 1) {
i = m;
j = m + 1;
res += 1.0;
} else {
i = m - 1;
j = m + 1;
}
// do the check:
while ((i >= 0) && (j < n)) {
// update the probability
if (s[i] == '?' || s[j] == '?') {
p *= 1.0 / 26.0;
} else if (s[i] != s[j]) {
p = 0;
}
res += p;
i--;
j++;
}
}
}
return res;
}
CombinationLockDiv1
Problem Details
Used as: Division One - Level Two:
Value | 475 |
Submission Rate | 173 / 720 (24.03%) |
Success Rate | 30 / 173 (17.34%) |
High Score | tourist for 424.38 points (10 mins 3 secs) |
Average Score | 260.68 (for 30 correct submissions) |
Let’s use the solution for the division 2 version as a starting point. `O(n^3)` is too heavy for this problem `(n <= 2500)`. But we can optimize it with a few ideas.
In the division 2 solution we use a loop to visit all possibilities of `y` and consider the ones that set the digit to 0. In reality, though modular arithmetic, it is easy to find a number `t` such that if we put `t`, `t+10`, or `t+20`, intervals through the digit the digit will be set to 0.
Once `t` is known, we can reach a number of operations modulo `t` either by opening new intervals or closing them. The key to optimizing this problem is to notice that the number of new intervals or closed intervals should be as small as possible.
If we are adding intervals, the number of intervals we add should be as small as possible. If adding `a` intervals is good enough for this digit, and we need more intervals for a future digit, we can always add them when that future digit is reached.
If we are removing intervals, the number of removed intervals should also be as small as possible. This time it is clear, because if we remove more intervals than necessary for the current digit, a future digit that needs more intervals would increase the cost without need.
The minimum number of intervals to add or remove, can be found through modular arithmetic and is between 0 and 9. Now each digit has 3 decision: Change direction, add intervals or remove intervals. We need `O(1)` operations for each state of the `f(p,x,u)` function. Effectively reducing the complexity to `O(n^2)`.
Remember that there is a heavy constant factor in the current approach, because the number of open intervals is at most 9*n. We might need to optimize memory - which means we need iterative dynamic programming - and make sure to do crop as many states as possible when doing the dynamic programming.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
static
const int INF = 1000000000;
static
const int MAX_N = 2500;
static
const int MAX_OP = 2500 * 9;
vector < int > d;
int n;
int dp[2][MAX_OP + 1][2];
int minimumMoves(string s, string t) /* assume we already merged the strings together */ {
n = s.size();
d.resize(n);
for (int i = 0; i < n; i++) {
if (s[i] >= t[i]) {
d[i] = s[i] - t[i];
} else {
d[i] = s[i] + 10 - t[i];
}
}
for (int p = n; p >= 0; p--) {
for (int x = 0; x <= p * 9; x++) {
for (int up = 0; up <= 1; up++) {
// ignore invalid tuples (p,x,up), greatly cuts execution time
int prev = ((p == 0) ? 0 : d[p - 1]);
if ((up == 1) && ((prev + x) % 10 != 0)) {
continue;
}
if ((up == 0) && ((prev + 9 * x) % 10 != 0)) {
continue;
}
int & res = dp[p & 1][x][up];
if (p == n) {
res = 0;
} else {
res = INF;
int np = !(p & 1);
if (up == 1) {
// previous step was up
// try up:
int add = 9 * (d[p] + x) % 10;
if (add + x <= (p + 1) * 9) {
res = std::min(res, add + dp[np][x + add][1]);
}
int rem = (d[p] + x) % 10;
if (rem <= x) {
res = std::min(res, dp[np][x - rem][1]);
}
// try down:
int z = d[p];
res = std::min(res, z + dp[np][z][0]);
} else {
// previous step was down
// try down:
int add = (d[p] + 9 * x) % 10;
if (x + add <= (p + 1) * 9) {
res = std::min(res, add + dp[np][x + add][0]);
}
int rem = (x + 9 * d[p]) % 10;
if (rem <= x) {
res = std::min(res, dp[np][x - rem][0]);
}
// try up:
int z = (9 * d[p]) % 10;
res = std::min(res, z + dp[np][z][1]);
}
}
}
}
}
return dp[0][0][0];
}
In fact, it appears that the maximum number of moves per digit is around 5000. If you can prove this, it can cut the constant factor enough to allow even memoization and a brute force search for the values of add and rem:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
static
const int INF = 1000000000;
static
const int MAX_N = 2500;
static
const int MAX_OP = 5500;
vector < int > d;
int n;
int dp[MAX_N + 1][MAX_OP + 1][2];
int rec(int p, int x, int up) {
int & res = dp[p][x][up];
if (res == -1) {
if (p == n) {
res = 0;
} else {
res = INF;
if (up == 1) {
// previous step was up
// try up:
// (these search loops for correct add/rem value can be
// replaced by just a modular operation)
for (int add = 0; add <= 9 && x + add <= MAX_OP; add++) {
if ((d[p] + x + add) % 10 == 0) {
//we can !
res = std::min(res, add + rec(p + 1, x + add, 1));
}
}
for (int rem = 0; rem <= 9 && rem <= x; rem++) {
if ((d[p] + x - rem) % 10 == 0) {
//we can !
res = std::min(res, rec(p + 1, x - rem, 1));
}
}
// try down:
int z = d[p];
res = std::min(res, z + rec(p + 1, z, 0));
} else {
// previous step was down
// try down:
for (int add = 0; add <= 9 && x + add <= MAX_OP; add++) {
if ((d[p] + 9 * (x + add)) % 10 == 0) {
//we can !
res = std::min(res, add + rec(p + 1, x + add, 0));
}
}
for (int rem = 0; rem <= 9 && rem <= x; rem++) {
if ((d[p] + 9 * (x - rem)) % 10 == 0) {
//we can !
res = std::min(res, rec(p + 1, x - rem, 0));
}
}
// try up:
int z = (9 * d[p]) % 10;
res = std::min(res, z + rec(p + 1, z, 1));
}
}
}
return res;
}
int minimumMoves(string s, string t) {
n = s.size();
d.resize(n);
for (int i = 0; i < n; i++) {
if (s[i] >= t[i]) {
d[i] = s[i] - t[i];
} else {
d[i] = s[i] + 10 - t[i];
}
}
memset(dp, -1, sizeof(dp));
return rec(0, 0, 0);
}
Take a look to the forum discussion about this problem, in which we also discuss alternative approaches: forum thread
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 1 / 720 (0.14%) |
Success Rate | 0 / 1 (0.00%) |
High Score | null for null points (NONE) |
Average Score | No correct submissions |
The first obstacle to solving this problem is that it asks to return the k-th smallest total distance. There are infinitely many distances, so what can we do about this?
It is often useful to reduce problems that ask for the k-th element in some infinite sequence into counting problems. What if we could count the number of valid ways to connect the nails using a rope smaller than or equal to a bound. Then we could binary search for the smallest bound such that the result is at least K. This would effectively find the K-th length.
A counting problem is probably going to be easier to solve. Note that the binary search adds a factor. Since the result is floating point, we should do plenty of iterations. So the sub-problem’s solution will have less allocated time.
We have a length bound what’s the number of ways to connect that don’t exceed it?
This requires further analysis. A connection between the nails might have a possibly complex path and the distances are not necessarily integral (In fact, they are always irrational).
We should take a look to some valid solutions and look for any special property:
If we see the problem as moving from one nail to the other, we can catch four kinds of allowed “moves”, which always have the same length:
`e` : Minimum length of rope that goes between nail and the bottom or top of the first or the last disk. All rope lengths will contain `2e` in their sum. We’ll need geometry to find it.< /li>
`A`: The distance between the tops of two consecutive disks, also the distance between the bottoms of two consecutive disks. Turns out `A = d`.
`B`: The minimum rope length between the top of a circle and the bottom of the next consecutive circle. We can find this one through some geometry.
`R`: Half the length of one of the circles.
The rope length will be a sum `2e + xA + yB + zR`. This is very useful because we can now count the number of ways to make a rope that uses triple `(x,y,z)`. For each bound in the binary search, we can pick all possible triples `(x,y,z)` such that `2e + xA + yB + zR <= “bound”`. Our new sub-problem is to count the number of ways to use a triple `(x,y,z)` of moves.
How many valid ways are there if we do `x` “A” moves, `y` “B” moves and `z` “C” moves in total? If we call them moves, then we should picture them as changing the state. Then we should consider how the moves modify the state. At first, the state is the left nail. A sequence of moves needs to turn the state into the right nail.
At first an “e” move makes us move from the left nail to the top or bottom of disk 1.
When in the top or bottom of a disk, we can use “A” moves to move from the current disk to the next disk.
“B” moves make you move from the bottom of a disk to the top of the next disk, or vice versa.
However, some moves change the direction, at first the direction is from left to right, but if we use a “R” move, besides of moving from the top to the bottom of the current disk (or vice versa) we also change to the opposite direction.
At the end, we can move from disk `n` to the right nail using an “e” move.
At this moment the state is composed of 3 variables: Position, direction and whether we are at the top or bottom of a disk. Since the challenge is to count the number of ways to solve with a triple `(x,y,z)` specifying the number of moves, we need to add the current values `(x,y,z)` to the state. This makes the state quite complex but it can be simplified:
The first thing to notice is that, in regards to the counting problem, the following two situations are symmetric:
Whether you are on top or at the bottom of a disk, it doesn’t change your available moves later, so we don’t need to differentiate between the bottom and top.
The direction is, however, important because it determines the index of the disk you are allowed to move to. However, the trick here is that the direction depends solely on the number of “R” moves we did in the past. “R” is the only move that changes the direction and it always toggles it. If the number of “R” moves is even, direction is left to right, else it is right to left.
Once we notice that the top and bottom function just the same, we can notice that for the counting problem, “A” and “B” moves work just the same. When we want to know if a triple `(x,y,z)` should be counted, the difference does matter. However, imagine if we counted the number of ways to do `w = x + y` “A” or “B” moves. Then we could multiply it by `((x+y),(y))`, where `((n),(k))` is the binomial coefficient to find the number of ways to do it using `x` “A” moves and `y` “B” moves.
We define the state as `(p, w,z)` where `p` is the position (0 is the first disk, `n-1` is the last disk). `w` is the number of “A” or “B” moves, we will call them forward moves and `z` is the number of “R” moves, we will call them direction toggles.
Assume we already know the number of ways for `(p, w, z)`. If we are currently in position `p`, we made `w` forward moves and `z` direction changes.
If `p = n-1`, this is the last disk and we can move to the right nail. This means that each known sequence that reaches `(n-1, w,z)` can be a solution.
We can move forward: forward means incrementing `p` if `z` is even or decreasing it if it is odd. This is not valid if there is no disk in the next position. It also means incrementing `w`. So we can increase the result. The result for `(p,w,z)` is added to the result for `(p’,w+1,z)`.
We can also toggle the direction, the result for `(p,w,z)` is added to the result for `(p,w,z+1)`.
Initially, we move from the left nail to disk 0, there are two ways to do it. This is the base case, the result for `(0, 0, 0)` is 2.
This builds a fairy simple dynamic programming, however, we should take a look to the maximum values of `w` and `z` we might need.
As `w` increases, the number of valid ways increases significantly. For example, for `w = 10`, we need to consider all pairs `(x,y)` of “A” and “B” moves. For each of those pairs, we have `((w),(x))` different ways to do it. If for a `w` , the number of valid ropes is larger than `K`, we do not really need to calculate for larger `w` values. `K <= 10^18`. Note that adding `((w),(x))` for each `(x <= w)` is equivalent to raising `2^x`. This means that we only need `w` as large as `log(K)` ( Because `K` is as large as 64 bits, we can be safe ignoring any `w` that is much larger than 64, like 70).
The maximum number of “R” moves needed can actually be very large: Imagine a disk radius that was much smaller than `d`. The rope circles around the same disk many times, each increasing the length by a negligible one, which means that even for small distances, it could be necessary to use very large values of `R`.
We can work around this by noticing that the culprit is wrapping around the disks. If we ignored cases that had two consecutive “R” moves, then each “R” move would be followed by an “A” or “B” move, effectively limiting the amount of “R” moves.
Ignoring wrap-around, requires us to include a new variable in the state that has 2 values and says whether or not the previous move was an “R” move.
But if we ignore the wrap-around cases when counting them in the dynamic programming, we need to include them somehow in the answer for the number of cases with length smaller than or equal to `K`. What we can do, is after finding the number of results for `(x,y,z)`, we find their length `L`, there is a slack `“bound” - L"` rope length that can be used by wrap-around moves. Up to `(“bound” - L") / (2R)` additional wrap-around moves can be added. They should be added after the “A” or “B” moves, we can find the number of ways to mix them using combinatorics.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
const long INF = (1 LL << 60);
double A, B, R;
long C[100000][40]; // we'll store some precalculated binomial coefficients here
long dp[80][80][60][2]; // AB, R, pos, prev turn
// When result is larger than K, we don't need to know the specific value,
// so we should try to always find min(K, result)
// in practice, doing all calculations in this way can be tedious so we use an infinite
// value smaller than the possible K but that allows additions and multiplication by 2
// this needs some extra workarounds, hence the 1.1...
long comb(long N, int K) {
// Return the binomial coefficient
if (N - K < K) {
K = N - K;
}
if (K == 0) {
return 1;
}
if (K == 1) {
return N;
}
if (K == 2 && 1.0 / 2.0 * N * (N - 1) < 1.1 * INF) {
return N * (N - 1) / 2;
}
if (K == 3 && 1.0 / 6.0 * N * (N - 1) * (N - 2) < 1.1 * INF) {
return N * (N - 1) * (N - 2) / 6;
}
if (K < 40 && N < 100000) {
return C[N][K];
}
return INF;
}
long func(int N, double bound) {
int i, j, k;
long ans = 0;
// For (i: number of AB moves, j: number of R moves):
for (i = 0; i < 70; i++)
for (j = 0; j < 70; j++)
if (dp[i][j][N - 1][0] != 0) {
// pick number of A moves:
for (k = 0; k <= i; k++) {
double L = A * k + B * (i - k) + R * j;
if (L > bound) {
continue;
}
// up to tmp extra wrap around moves can be made
long tmp = (long)((bound - L) / 2.0 / R);
// Pick the k "A" moves out of i forward moves
long cnt1 = comb(i, k);
// pick extra wrap around moves:
long cnt2 = comb(tmp + i + 1, i + 1);
// too large?
if (cnt2 > INF / dp[i][j][N - 1][0] / cnt1) {
return INF;
}
// add
ans += cnt1 * cnt2 * dp[i][j][N - 1][0];
if (ans > INF) {
return INF;
}
}
}
return ans;
}
double getLength(int d, int r, int N, long K) {
int i, j, k, p;
A = d;
B = sqrt((double) d * d - 4.0 * r * r) + 2.0 * r * asin(2.0 * r / d);
R = r * acos(-1.0);
double extra = sqrt((double) d * d - (double) r * r) + r * asin((double) r / d);
if (N == 1) {
//special case, there are no A or B moves...
return (K - 1) / 2 * 2.0 * R + 2.0 * extra;
}
for (i = 0; i < 100000; i++)
for (j = 0; j < 40; j++) {
if (j == 0 || j == i) {
C[i][j] = 1;
}
if (j > 0 && j < i) {
C[i][j] = min(C[i - 1][j - 1] + C[i - 1][j], INF);
}
}
dp[0][0][0][0] = 2;
for (i = 0; i < 70; i++)
for (j = 0; j < 70; j++)
for (k = 0; k < N; k++)
for (p = 0; p < 2; p++) {
if (p == 0) {
// toggle direction
dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1] + dp[i][j][k][p], INF);
}
if (j % 2 == 0 && k + 1 < N) {
// move forward, direction is right
dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0] + dp[i][j][k][p], INF);
}
if (j % 2 == 1 && k > 0) {
// move forward, direction is left
dp[i + 1][j][k - 1][0] = min(dp[i + 1][j][k - 1][0] + dp[i][j][k][p], INF);
}
}
// binary search:
double low = 0.0, high = 1000.0 * A;
for (i = 0; i < 50; i++) {
double mid = (low + high) / 2.0;
if (func(N, mid) >= K) {
high = mid;
} else {
low = mid;
}
}
return high + 2.0 * extra;
}